

class Heap {
    constructor(len) {
        this.pq = new Array(len + 1)
        this.N = 0
    }

    insert(val) {
        // 注意是从1开始
        this.pq[++this.N] = val
        this.swim(this.N)
    }
    popMax() {
        if (this.N <= 0) return -1
        let max = this.pq[1]
        this.swap(1, this.N)
        this.N--
        this.sink(1)
        return max
    }

    swim(k) {
        let p
        while (k > 1 && this.less(p = Math.floor(k / 2), k)) {
            this.swap(p, k)
            k = p
        }
    }
    sink(k) {
        while (2 * k <= this.N) {
            let p = 2 * k
            if (p < this.N && this.less(p, p + 1)) p += 1
            if (!this.less(k, p)) break
            this.swap(k, p)
            k = p
        }
    }

    less(i, j) {
        return this.pq[i] < this.pq[j]
    }

    swap(i, j) {
        let p = this.pq[i]
        this.pq[i] = this.pq[j]
        this.pq[j] = p
    }

    toString() {
        return this.pq.toString()
    }

}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
    let heap = new Heap(nums.length)
    nums.map(val => heap.insert(val))
    let max
    while (k > 0) {
        max = heap.popMax()
        k--
    }
    return max
};


console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 1))